/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-10-05
 * Time:20:24
 */

/**
 * 力扣剑指offer10-1:斐波那契数列
 */

public class fib {
    public int fib(int n) {
        //超出时间限制
//        if(n == 0){
//            return 0;
//        }
//        if(n == 1 || n == 2){
//            return 1;
//        }
//        if(n > 2){
//            return fib(n - 1) + fib(n - 2);
//        }
//        return -1;
        /**
         * 动态规划
         */
        //1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
        final int MOD = 1000000007;
        if (n < 2){
            return n;
        }
        int p = 0;
        int q = 0;
        int end = 1;
        for (int i = 2; i <= n; i++) {
            p = q;
            q = end;
            end = (p + q)%MOD;
        }
        return end;
    }
}
